public class Solution188 {
    public int maxProfit(int k, int[] prices) {
        int[] f1=new int[prices.length];
        int[] f2=new int[prices.length];
        int ans=0;
        for (int i=0;i<Math.min(k,prices.length);i++){
            f1[i]=-prices[i];
            for (int j=i+1;j<prices.length;j++){
                f1[j]=Math.max(f1[j-1],f2[j-1]-prices[j]);
            }
            f2[i]=0;
            for (int j=i+1;j<prices.length;j++){
                f2[j]=Math.max(f2[j-1],f1[j-1]+prices[j]);
            }
            ans=Math.max(ans,f2[prices.length-1]);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution188().maxProfit(2,new int[]{3,2,6,5,0,3}));
    }
}
